package main

/**
https://blog.csdn.net/My_Jobs/article/details/43451187
对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历
*/
func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}

	count := 0
	var dfs func(*TreeNode, int)
	dfs = func(root *TreeNode, sum int) {
		if root == nil {
			return
		}
		if root.Val == sum {
			count++
		} //注意这里不是else 因为有这种情况 sum:10    a:2 b:8 c:0   a+b已经满足了 count++ 但是a+b+c也满足 count需要再++

		dfs(root.Left, sum-root.Val)
		dfs(root.Right, sum-root.Val)

	}
	dfs(root, sum)
	return count + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

func main() {

}
